//
// Description: 5856. 完成任务的最少工作时间段
// Created by Loading on 2021/8/29.
//

#include <bits/stdc++.h>

using namespace std;

int minSessions(vector<int> &tasks, int sessionTime) {
    constexpr int INF = 15;
    int n = tasks.size();
    // 将所有任务状态压缩成长度为 n 的二进制形式，0 表示未选中此任务，1 表示选中此任务
    int max_ = 1 << n;
    // dp[i] 表示在 i 状态下，最小花费的时间段
    vector<int> dp(max_, INF);
    dp[0] = 0;

    // 初始值，将可以在一个时间段内完成的状态 dp 值置为 1
    for (int i = 1; i < max_; ++i) {
        int temp = i, index = 0, cost = 0;
        while (temp) {
            if (temp & 1) {
                cost += tasks[index];
                // 已经不可能在一个时间段内完成，直接跳出
                if (cost > sessionTime) {
                    break;
                }
            }
            temp >>= 1;
            ++index;
        }
        // 选中的任务加起来不超过 sessionTime，这些任务可以在同一时间段完成
        if (cost <= sessionTime) {
            dp[i] = 1;
        }
    }

    // 更新 dp 数组
    for (int i = 1; i < max_; ++i) {
        // 已经最优，无需更新
        if (dp[i] == 1) {
            continue;
        }
        // 枚举二进制子集
        for (int j = (i - 1) & i; j > 0; j = (j - 1) & i) {
            dp[i] = min(dp[i], dp[j] + dp[i - j]);
        }

        // 暴力枚举
//        for (int j = 1; j < i; ++j) {
//            // 判断 j 是否为 i 的子集
//            if ((i | j) == i) {
//                // i 状态下的最优解可以由两个 i 的子集求和给出
//                dp[i] = min(dp[i], dp[j] + dp[i - j]);
//            }
//        }
    }

    return dp[max_ - 1];
}

int main() {
    vector<int> tasks = {1, 2, 10, 10, 3};
    int sessionTime = 15;
    int res = minSessions(tasks, sessionTime);
    cout << res << endl;

    return 0;
}